package bin_tree;

public class MyBinaryTree {
    // 孩子兄弟表示法
    private static class Node {
        private char val;
        private Node left;
        private Node right;
        public Node(char val) {
            this.val = val;
        }
    }

    // 生成一个测试二叉树
    public Node buildATree() {
        Node nodeA = new Node('A');
        Node nodeB = new Node('B');
        Node nodeC = new Node('C');
        Node nodeD = new Node('D');
        Node nodeE = new Node('E');
        Node nodeF = new Node('F');
        Node nodeG = new Node('G');
        Node nodeH = new Node('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.left = nodeG;
        nodeG.right = nodeH;
        nodeC.right = nodeF;
        return nodeA;
    }
    // 先序遍历(输出内容)
    // 根左右
    // 传入一个二叉树的根节点，根据先序遍历访问该树
    public void preOrder(Node root) {
        if (root == null) {
            return;
        }
        // 根
        System.out.print(root.val +" ");
        // 左树
        preOrder(root.left);
        // 右树
        preOrder(root.right);
    }

    /**
     * 传入一个二叉树的根节点root，根据中序遍历访问该树
     * 左根右
     * @param root 传入的根节点
     */
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        // 先按照中序遍历访问左子树
        inOrder(root.left);
        System.out.print(root.val + " ");
        // 按照中序再访问右子树
        inOrder(root.right);
    }

    /**
     * 按照后序遍历访问二叉树
     * @param root
     */
    public void postOrder(Node root) {
        if (root == null) {
            return;
        }
        // 先左
        postOrder(root.left);
        // 再右
        postOrder(root.right);
        System.out.print(root.val +" ");
    }

    /**
     * 传入一个二叉树的根节点，求出该二叉树的节点个数
     * @param root 二叉树的根节点
     * @return
     */
    public int getNodeCount(Node root) {
        if (root == null) {
            return 0;
        }
        return 1 + getNodeCount(root.left) + getNodeCount(root.right);
    }

    /**
     * 传入一个二叉树根节点root，就能求得该二叉树的叶子节点个数
     * @param root 传入根节点
     * @return
     */
    public int getLeafNodeCount(Node root) {
        // 空树
        if (root == null) {
            return 0;
        }
        // 只有根节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 此时二叉树不为空且有子树
        // 此时二叉树叶子节点个数 = 左树叶子节点个数 + 右树的叶子节点个数
        return getLeafNodeCount(root.left)
                + getLeafNodeCount(root.right);
    }

    /**
     * 传入一个根节点root，就能求得该树高度
     * @param root 传入二叉树根节点
     * @return
     */
    public int height(Node root) {
        if (root == null) {
            return 0;
        }
        // 左树高度 height(root.left) -> 以root.left为根节点的高度
        // 二叉树不为空 1 + Math.max(左树高度，右树高度);
        return 1 + Math.max(height(root.left),height(root.right));
    }

    /**
     * 判断一颗以root为根节点的二叉树中是否包含值为val的节点
     * @param root
     * @param val
     * @return
     */
    public boolean contains(Node root,char val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        // 在左树或右树中寻找val
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 传入一个二叉树的根节点root，求出第k层节点个数
     * @param root
     * @param k
     * @return
     */
    public int getKLevelNodes(Node root,int k) {
        if (k <= 0 || root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodes(root.left,k - 1) +
                getKLevelNodes(root.right,k - 1);
    }



    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        Node root = myBinaryTree.buildATree();
        System.out.println("先序遍历结果:");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("-----------------");
        System.out.println("中序遍历结果:");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("------------------");
        System.out.println("后序遍历结果:");
        myBinaryTree.postOrder(root);
        System.out.println("二叉树节点个数为:");
        System.out.println(myBinaryTree.getNodeCount(root));
        System.out.println("二叉树的叶子节点个数为:");
        System.out.println(myBinaryTree.getLeafNodeCount(root));
        System.out.println("二叉树的高度为:");
        System.out.println(myBinaryTree.height(root));
        System.out.println(myBinaryTree.contains(root,'H'));
        System.out.println(myBinaryTree.contains(root,'X'));
        System.out.println("二叉树第4层节点个数:");
        System.out.println(myBinaryTree.getKLevelNodes(root,4));
    }
}
